package com.lw.leetcode.arr.b;

import java.util.HashMap;
import java.util.Map;

/**
 * 974. 和可被 K 整除的子数组
 *
 * @Author liw
 * @Date 2021/6/21 17:58
 * @Version 1.0
 */
public class SubarraysDivByK {

    public static void main(String[] args) {
        SubarraysDivByK test = new SubarraysDivByK();

        //  [4,5,0,-2,-3,1], K = 5   7
        int[] arr = {4,5,0,-2,-3,1};
        int k = 5;

        // [4,5,0,67,3,765,76,9,-2,-3,1]  42   3
//        int[] arr = {4,5,0,67,3,765,76,9,-2,-3,1};
//        int k = 42;
        int i = test.subarraysDivByK(arr, k);
        System.out.println(i);

    }

    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>(k);
        int item = 0;
        map.put(0, 1);
        Integer value;
        int sum = 0;
        for (int num : nums) {
            item = (item + num) % k;
            if (item < 0) {
                item += k;
            }
            value = map.get(item);
            if (value == null) {
                map.put(item, 1);
            } else {
                map.put(item, value + 1);
                sum += value;
            }
        }
        return sum;
    }
}
